(파이썬 S/W 문제해결 기본) Stack1 - 4869번 4866번 4871번 4873번

4869번 - 종이붙이기

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

피보나치 수열과 비슷

# def paper_paste(s):

# if s == N:

# return 1

# if s > N:

# return 0

# return paper_paste(s+10) + paper_paste(s+20)\*2

def paper_paste(s):
arr = [0]\*(s//10)
arr[0] = 1
arr[1] = 3

    for i in range(2, s//10):
        arr[i] = arr[i-1] + arr[i-2]*2

    return arr[s//10-1]

T = int(input())

for test_case in range(1, T+1):
N = int(input())

    print('#{} {}'.format(test_case, paper_paste(N)))

**

---

4866번 - 괄호검사

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

stack을 활용한 괄호검사

def count_parenthesis(line):
stack = []

    for key in line:
        if key == "(" or key == "{":
            stack += key
        elif key == ")" or key == "}":
            if len(stack) == 0:
                stack += key
                break
            elif key == ")" and stack[-1] == "(":
                stack.pop()
            elif key == "}" and stack[-1] == "{":
                stack.pop()
            else:
                stack += key
                break
    isPare = 0
    if len(stack) == 0:
        isPare = 1

    return isPare

T = int(input())

for test_case in range(1, T+1):
input_line = input()

    print('#{} {}'.format(test_case, count_parenthesis(input_line)))

---

4871번 - 그래프 경로

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

graph와 DFS
BFS는 queue를 사용하고, DFS는 stack을 사용함

def makeGraph(V, E): # 정점 번호를 key값, set()를 value값으로 갖는 기본 그래프 # ex) {1:set(), 2:set(), 3:set()}
graph = {key+1:set() for key in range(V)}

    # 정점(V)에 연결된 다음 노드(E) 입력, 그래프 수정
    # ex) {1:{3, 4, 6}, 2:{3}, 3:set()}
    for _ in range(E):
        key, val = map(int, input().split())
        graph[key].add(val)
    return graph

def DFS(graph, V, E):
visited = []
stack = []

    stack.append(V)

    is_path = 0
    while stack:
        node = stack.pop()
        if node == E:
            is_path = 1
            break

        if node not in visited:
            visited.append(node)
            stack.extend(graph[node])
    return is_path

T = int(input())

for test_case in range(1, T+1): # V: 정점 E: 간선을 입력
V, E = map(int, input().split()) # 간선(E) 수 만큼 반복하며 딕셔너리형 그래프 만듬
myGraph = makeGraph(V, E)

    # 확인할 경로의 시작 정점과 끝 정점 입력
    cV, cE = map(int, input().split())
    # 깊이우선탐색으로 경로 확인
    ans = DFS(myGraph, cV, cE)

    print('#{} {}'.format(test_case, ans))

---

4873번 - 반복문자 지우기

• 시간 : 10개 테스트케이스를 합쳐서 Python의 경우 2초
• 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내

stack을 활용

T = int(input())

for test_case in range(1, T+1): # 일단 입력 받고
seq_string = list(input()) # 스택을 만들어서 한 단어씩 push, pop 한다
stack = []

    for word in seq_string:
        # 맨 처음 스택이 비어있을 때,
        if len(stack) == 0:
            stack.append(word)
        # 그 외, 새로 입력되는 문자와 스택 마지막 문자가 같으면 pop
        else:
            if stack[-1] == word:
                stack.pop()
            else:
                stack.append(word)

    print('#{} {}'.format(test_case, len(stack)))

---